<?php
#+------------------------------------------------------------------
#| 普通的。
#+------------------------------------------------------------------
#| Author:Janmas Cromwell <janmas-cromwell@outlook.com>
#+------------------------------------------------------------------
class LinkList
{
    protected $node;
    protected $size;

    public function __construct()
    {
        $this->init();
    }

    protected function init()
    {
        $this->node = new Node('Header');
        $this->size = 0;
    }

    /**
     * 添加
     * @param int $index
     * @param string $value
     */
    public function add(int $index, string $value)
    {
        if ($index == 0) {
            return $this->unshift($value);
        }
        $next = $this->node;
        for ($i = 0; $i < $index; ++$i) {
            $next = $next->next;
        }
        $node = new Node($value, $next, $this->node->next);
        $next->next = $node;
        $this->node->next->prev = $node;
        ++$this->size;
    }

    /**
     * 头部添加
     * @param $value
     */
    public function unshift($value)
    {
        $node = new Node($value, $this->node, $this->node);
        if (is_null($this->node->next)) {
            $this->node->prev = $this->node->next = $node;
        } else {
            $zero = $this->node->next;
            $zero->prev = $node;
            $node->next = $zero;
            for ($i = 0; $i < $this->size; $i++) {
                $next = $zero->next;
            }
            $next->next = $node;
        }
        $this->size++;
    }

    /**
     * 尾部添加
     * @param $value
     */
    public function push($value)
    {
        $next = $this->node->next;
        for ($i = 0; $i < $this->size; ++$i) {
            $next = $next->next;
        }

        $next->next = new Node($value, $next->prev, $next->next);
        $this->size++;
    }

    /**
     * 移除指定
     * @param $index
     * @throws Exception
     */
    public function remove($index)
    {
        if ($index > $this->size || $index < 0) {
            throw new Exception('索引超过链表长度');
        }
        $node = $this->node->next;
        for ($i = 0; $i <= $index; $i++) {
            if ($i == $index) {
                $prev = $node->prev;
                $next = $node->next;
                $prev->next = $next;
                $next->prev = $prev;
                $this->size--;
            }
            $node = $node->next;
        }
    }

    /**
     * 查找
     * @param $index
     * @throws Exception
     */
    public function select($index)
    {
        if ($index > $this->size || $index < 0) {
            throw new Exception('索引超过链表长度');
        }
        $node = $this->node->next;
        for ($i = 0; $i <= $index; $i++) {
            if ($i == $index) {
                return $node->data;
            }
            $node = $node->next;
        }
    }

    /**
     * 尾部弹出
     */
    public function pop()
    {

        $node = $this->node->next;
        for ($i = 1; $i <= $this->size; $i++) {
            if ($i == $this->size) {
                $prev = $node->prev;
                $next = $node->next;
                $prev->next = $next;
                $next->prev = $prev;
                $this->size--;
                return $node->data;
            }
            $node = $node->next;
        }
    }

    /**
     * 头部弹出
     * @return mixed
     */
    public function shift()
    {
        $node = $this->node->next;
        $prev = $node->prev;
        $next = $node->next;
        $prev->next = $next;
        $next->prev = $prev;
        $this->size--;
        $this->node = new Node('Header', $prev, $next);
        return $node->data;
    }

    /**
     * 反转链表
     */
    public function flip()
    {
        $node = $this->node->next;
        $i = 1;
        while ($i <= $this->size) {
        }
    }
    /**
     * 3 1 2
     * 1 2 3
     * 2 3 1
     *
     * 1 3 2
     * 3 2 1
     * 2 1 3
     *
     * 第一次循环
     * $current = clone $node 当前节点类 1
     * $node = $current->prev 前一个节点类 3
     * $node->prev = $current->next;
     * $node->next = $current
     *
     * $node = $current->next;
     *
     */
    /**
     * 转字符串
     * @return string
     */
    public function tostring()
    {
        return (string)$this;
    }

    public function __toString()
    {
        $node = $this->node->next;
        for ($i = 0; $i < $this->size; ++$i) {
            $r[] = $node->data;
            $node = $node->next;
        }

        return implode('<=>', $r);
    }

}
